package algogo

// Modify array in and out to generate the next
// k-combination of the n total elements of in and out.
// Arrays in and out must be sorted in ascending order.
// k elements are chosen from arrays in and out and placed in array in
// array in constitutes the chosen elements; out consitutes the remaining elements (sorted)
// Return true if the next combination exists, false otherse
// Upon returning false, array in is back to the lexicographical minimum
// Adapted from C++ std proposal WG21/N2639, Herve Bronnimann
// NB  Does not generate all combinations...
func combination(in, out []int) bool {
	i, j := len(in), len(out)
	if i == 0 || j == 0 {
		return false
	}

	// reverse-find the first element of in less than the last of out
	// otherwise, i == 0
	i--
	j--
	for ; i > 0 && in[i] >= out[j]; i-- {
	}

	result := (i == 0) && in[0] >= out[j]

	if !result {
		jj := 0
		for ; jj != j && in[i] >= out[jj]; jj++ {
		}
		in[i], out[jj] = out[jj], in[i]
		i++
		in = in[i:]
		jj++
		out = out[jj:]
	}

	if len(in) > 0 && len(out) > 0 {
		i = len(in)
		j = 0
		nout := len(out)
		for i != 0 && j != nout {
			i--
			in[i], out[j] = out[j], in[i]
			j++
		}
		Reverse(in[:i])
		Reverse(in)
		Reverse(out[j:])
		Reverse(out)
	}

	return !result
}

// NextCombination returns array a with a[:k] representing the next k-combination of a, where k <= n.
// To iterate through all k-combinations through repeated calls,
// array a must be initialized in ascending order
func NextCombination(a []int, k int) bool {
	return combination(a[:k], a[k:])
}

// PrevCombination returns array a with a[:k] representing the previous k-combination of a, where k <= n.
// To iterate through all k-combinations through repeated calls,
// array a must the last k-combination generated by NextCombination;
// that is, a[:k] is in descending order and a[k:] is in ascending order
func PrevCombination(a []int, k int) bool {
	return combination(a[k:], a[:k])
}
